package com.linyaonan.leetcode.medium._2187;

import java.util.Arrays;

/**
 *
 * 给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。
 *
 * 每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。
 *
 * 给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。
 *
 *
 *
 * 示例 1：
 *
 * 输入：time = [1,2,3], totalTrips = 5
 * 输出：3
 * 解释：
 * - 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。
 *   已完成的总旅途数为 1 + 0 + 0 = 1 。
 * - 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。
 *   已完成的总旅途数为 2 + 1 + 0 = 3 。
 * - 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。
 *   已完成的总旅途数为 3 + 1 + 1 = 5 。
 * 所以总共完成至少 5 趟旅途的最少时间为 3 。
 * 示例 2：
 *
 * 输入：time = [2], totalTrips = 1
 * 输出：2
 * 解释：
 * 只有一辆公交车，它将在时刻 t = 2 完成第一趟旅途。
 * 所以完成 1 趟旅途的最少时间为 2 。
 *
 *
 * 提示：
 *
 * 1 <= time.length <= 10^5
 * 1 <= time[i], totalTrips <= 10^7
 *
 * @author: Lin
 * @date: 2024/12/7
 */
public class MinimumTimeToCompleteTrips {

    /**
     * 从题目可以发现每一辆公交车都是独立的，假设有这么一组公交车(数值表示一趟需要的时间):[m1,m2,m3]
     * 那么在n的这个时间总共可以跑 m1/n + m2/n + m3/n 趟
     *
     * 题目要求需要完成totalTrips趟，最少的情况，那么简化后就是二分法的最左匹配问题
     * left：最少的公交车的时间 time[0]
     * right: 情况需要分析，假设一组m公交车中最长一趟的时间为mmax, 那么将这一批车的时间都规划为mmax，那么需要完成n趟的时间为 n * mmax
     *
     * 需要考虑输入范围int溢出的情况
     *
     * @param time
     * @param totalTrips
     * @return
     */
    public long minimumTime(int[] time, int totalTrips) {
        Arrays.sort(time);

        long l = time[0];
        long r = time[time.length - 1] * (long) totalTrips;

        long rr = r;

        while (l <= r) {
            long mid = l + (r - l) / 2;
            long temp = addCount(time, mid);
            if (temp >= totalTrips) {
                rr = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return rr;
    }

    public long addCount(int[] time, long mid) {
        long r = 0L;
        for (long i : time) {
            r += (mid / i);
        }
        return r;
    }

}
